package kcsj;

import sxx.MyUtil;

import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.Scanner;

public class TribeTroops {
    private final int n, m;//n个居民间有m个仇敌关系
    //    private int u, v;//居民u与居民v是仇敌
    private final int[][] x;//存储村民u和村民v关系的邻接矩阵
    private int numOfTroop;//部落部队的人数
    private final int[] f;//当前方案
    private final int[] bestf;//最佳方案
    private int selected;//已选人数
    private int[] result;//0号位置放部队人数,其余放部队人选

    public TribeTroops(int index) {
        InputStream fin = TribeTroops.class.getResourceAsStream("/data/TribeTroops/test/inde" + index + ".in");
        assert fin != null : "找不到测试数据!";
        Scanner scanner = new Scanner(fin);
        n = scanner.nextInt();
        m = scanner.nextInt();
        numOfTroop = 0;
        selected = 0;
        f = new int[n + 1];//0号位置不用
        bestf = new int[n + 1];//0号位置不用
        result = new int[n + 1];//0号位置放部队人数,1~n放部队人选
        Arrays.fill(f, 0);
        Arrays.fill(bestf, 0);
        x = new int[n + 1][n + 1];//0号位置不用
        for (int i = 0; i <= n; i++) {
            Arrays.fill(x[i], 1);
        }
        for (int i = 0; i < m; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            x[u][v] = x[v][u] = 0;
        }

        backtrace(1);//开始回溯
        //构造最优解
        result = Arrays.copyOf(bestf, bestf.length);
        result[0] = numOfTroop;

        scanner.close();
        try {
            fin.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private boolean noEnemies(int t) {
        //检查当前加进来的第t个村民是否和之前的居民存在仇敌关系
        for (int i = 0; i < t; i++) {
            //第i个人被选且不能与第t个人为仇敌
            if (f[i] == 1 && x[i][t] == 0) {
                return false;
            }
        }
        return true;
    }

    private void backtrace(int t) {
        if (t > n) {//达到叶子节点
            int temp = MyUtil.sumArray(f);
            if (temp > numOfTroop) {
                numOfTroop = temp;
                System.arraycopy(f, 0, bestf, 0, f.length);
            }
        } else {
            if (noEnemies(t)) {
                //进入左子树
                f[t] = 1;//第t个居民被选
                selected++;//当前已选人数
                backtrace(t + 1);
                selected--;
            }
            if (selected + n - t > numOfTroop) {//如果当前解的个数加上剩余解的个数还比最大解小，那么这个解无需搜索
                //进入右子树
                f[t] = 0;//第t个居民不被选
                backtrace(t + 1);
            }
        }
    }

    public int[] getResult() {
        return result;
    }

    public static void main(String[] args) {
        System.out.println("信计1902张倚睿");
        for (int i = 0; i <= 6; i++) {
            int[] result = new TribeTroops(i).getResult();
            System.out.println(result[0]);
            MyUtil.printA(result, 1);
            System.out.println();
        }
    }
}
